package com.example.practice.class04;

/**
 * @Date 2022/9/12
 * @Author Jonathan
 * @Description 返回一个数组中所选数字不能相邻的情况下最大子序列累加和
 */
public class Code04_MaxSubSequenceNoAdjacent {
    public static void main(String[] args) {
        int[] nums = new int[]{5, -1, -3, -2, -1, -3, 0};
        System.out.println(getMaxSubSequenceNoAdjacent(nums));
    }


    public static int getMaxSubSequenceNoAdjacent(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr, 0);
    }

    // todo  写成dp
    public static int process(int[] arr, Integer index) {
        if (index >= arr.length) {
            return 0;
        }
        // 当前位置要了的话 就看当前位置的加+2的情况
        int p1 = arr[index] + process(arr, index + 2);
        // 当前位置没要的话  下一个位置的情况
        int p2 = process(arr, index + 1);
        return Math.max(p1, p2);
    }
}
